package com.cat.greedyAlgorithm;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-number-of-integers-to-choose-from-a-range-i/
 * @create 2025/8/21 10:54
 * @since JDK17
 */

public class Solution04 {
    long get(int a1, int an, int n) {
        return (long)(a1 + an) * n / 2;
    }

    public int maxCount(int[] arr, int n, int maxSum) {
        int m = arr.length + 2, ans = 0;
        long sum = 0, t;
        int[] banned = new int[m];
        for (int i = 1; i < m - 1; i++) {
            banned[i] = arr[i - 1];
        }
        banned[m - 1] = n + 1;
        Arrays.sort(banned);
        for (int i = 1; i < m; i++) {
            if (banned[i] > n) {
                banned[i] = n + 1;
            }
            if (banned[i] - banned[i - 1] <= 1) {
                continue;
            }
            t = get(banned[i - 1] + 1, banned[i] - 1, banned[i] - banned[i - 1] - 1);
            if (sum + t <= maxSum) {
                sum += t;
                ans += banned[i] - banned[i - 1] - 1;
            } else {
                for (int j = banned[i - 1] + 1; j < banned[i]; j++) {
                    if (sum + j > maxSum) {
                        return ans;
                    } else {
                        ans++;
                        sum += j;
                    }
                }
            }
        }
        return ans;
    }

    public int maxCount01(int[] banned, int n, int maxSum) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : banned) {
            set.add(num);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (set.contains(i)) {
                continue;
            }
            maxSum -= i;
            if (maxSum < 0) {
                return ans;
            }
            ans++;
        }
        return ans;
    }
}
